package sort;

import java.util.Arrays;

public class Heap {
    private static final int DEFAULT_CAPACITY = 11;

    private int[] queue;

    // size表示有效数据个数(即堆中实际存在的元素,而不是空的空间)
    private int size;

    public Heap() {
        //构造方法, 给堆初始化容量
        this.queue = new int[DEFAULT_CAPACITY];
    }

    // 1.初始化queue
    public void InitQueue(int[] arr) {
        // 判断一下是否要扩容
        if (arr.length > DEFAULT_CAPACITY) {
            queue = new int[arr.length];
        }
        for (int i = 0; i < arr.length; i++) {
            queue[i] = arr[i];
            size++;
        }
    }

    // 2.创建堆(向下调整)
    public void createHeap() {
        // size 是有效数据的个数, 也是这个堆的长度
        // size-1 表示拿到最后一个叶节点
        // (size-1-1) / 2 就是二叉树的性质五, 拿到叶节点的父节点
        // 当 parent 为 0 时, 还需要进行调整
        for (int parent = (size - 1 - 1) / 2; parent >= 0; parent--) {
            shiftDown(parent, size);
        }
    }

    // 向下调整
    private void shiftDown(int parent, int size) {
        // 通过 parent 下标结点拿到左孩子节点
        int child = 2 * parent + 1;
        while (child < size) {
            // 如果存在 child节点 才能进入循环进行调整堆结构
            if (child + 1 < size && queue[child] < queue[child + 1]) {
                // 如果存在右孩子节点, 并且右节点的值比左节点的大, 则选中右节点
                child = child + 1;
            }
            // 向下调整, 如果 child >= size 说明当前根节点没有子节点了
            if (queue[child] < queue[parent]) {
                // 构建小根堆, 如果子节点值比根节点的小, 则子节点变更为父节点, 父节点变更为子节点
                swap(child, parent);
                // 向下调整: child下标节点成为父节点, parent 指向child, 而child又去指向当前父节点的子节点
                parent = child;
                child = 2 * parent + 1;
            }else {
                // 如果父节点就是最小的节点,那么当前堆结构就是小根堆
                // 如果当前是小根堆结构, 那么其下面的子树一定也是小根堆结构, 因为我们是从最后一个非叶节点开始调整的
                break;
            }
        }

    }

    private void swap(int child, int parent) {
        int tmp = queue[child];
        queue[child] = queue[parent];
        queue[parent] = tmp;
    }

    // 堆的插入, 向上调整
    public void offer(int val) {
        if (isFull()) {
            // 如果队列满了, 则扩容
            grow();
        }
        // i 指向插入元素应该插入的位置
        int i = size;
        if (i == 0) {
            // 如果队列中没元素, 则直接插在0下标位置
            queue[0] = val;
        }else {
            // 如果有, 则通过向上调整来插入元素
            siftUp(val, i);
        }
        // 有效数据+1
        size++;
    }

    private void siftUp(int val, int child) {
        // 向上调整本质上是一个插入排序, 将val作为牌
        // 找到val这张牌应该插入的位置
        while (child > 0) {
            // child == 0 说明已经到了根节点
            int parent = (child - 1) / 2;
            if (val < queue[parent]) {
                queue[child] = queue[parent];
                child = parent;
            }else {
                // 如果不大于, 此时child所在位置就是val应该插入的位置
                break;
            }
        }
        queue[child] = val;
    }

    // 堆的删除
    public int pull() {
        if (size == 0) {
            // 如果队列本身为空, 抛出异常说明
            throw new IndexOutOfBoundsException("队列为空,无法删除");
        }
        // 删除的是堆顶元素, 用一个值保存起来
        int result = queue[0];
        // 交换堆顶元素和最后一个元素
        swap(0,size-1);
        // 交换后对对顶元素进行向下调整(注意此时堆中元素已经少了一个)
        shiftDown(0,size-1);
        size--;
        return result;
    }

    private void grow() {
        // 二倍扩容
        queue = Arrays.copyOf(queue, queue.length * 2);
    }

    private boolean isFull() {
        return size == queue.length;
    }
}
